﻿#include <iostream>
#include <queue>

using namespace std;

//⼩红的⼝罩（贪⼼+堆）
//https://ac.nowcoder.com/acm/problem/229953

//int main()
//{
//	int n, k;
//	cin >> n >> k;
//
//	priority_queue<int, vector<int>, greater<int>> heap;
//
//	for (int i = 0; i < n; i++)
//	{
//		int x;
//		cin >> x;
//		heap.push(x);
//	}
//
//	int sum = 0, cnt = 0;
//	while (true)
//	{
//		int uncomfortable = heap.top();
//		heap.pop();
//		sum += uncomfortable;
//		if (sum <= k)
//		{
//			heap.push(uncomfortable * 2);
//			cnt++;
//		}
//		else
//			break;
//	}
//	cout << cnt;
//}


//春游（模拟-分情况讨论）
//https://ac.nowcoder.com/acm/problem/219035

//long long func()
//{
//	long long n, a, b;
//	cin >> n >> a >> b;
//	
//	long long ret = 0;
//	if (n <= 2)
//	{
//		return min(a, b);
//	}
//	if (a * 3 < b * 2)//选择a双人船
//	{
//		ret += n / 2 * a;
//		n %= 2;
//		if(n)
//			ret += min(min(a, b), b - a);//多租一条或者凑一船3个人
//	}
//	else//选择b三人船
//	{
//		ret += n / 3 * b;
//		n %= 3;
//		if (n)
//		{
//			if (n == 1)
//				ret += min(min(a, b), a * 2 - b);
//			if (n == 2)
//				ret += min(min(a, b), a * 3 - b);
//		}
//	}
//	return ret;
//}
//
//int main()
//{
//	int t;
//	cin >> t;
//	while (t--)
//	{
//		cout << func() << endl;
//	}
//}


// 数位染⾊（动态规划-01背包）
// https://www.nowcoder.com/practice/adf828f399de4932955734a4eac12757?tpId=230&tqId=38956&ru=/exam/oj

// dp[i][j]=dp[i-1][j]||dp[i-1][j-arr[i]]
// 每一层i都只依赖上一层的i，二维数组空间优化为一维数组
// dp[j]=dp[j]||dp[j-arr[i]]
// 每一个j都只依赖自己这一列以及之前的j，倒序更新数组，防止更新的值代替上一层的值参与计算

//const int N = 20, M = N * 9;
//long long x;
//int n, sum;
//int arr[N];
//bool dp[M];
//
//bool func()
//{
//	if (sum % 2 == 1)
//		return false;
//	sum /= 2;
//	dp[0] = true;
//	for (int i = 0; i < n; i++)
//	{
//		// j必须大于arr[i]
//		for (int j = sum; j >= arr[i]; j--)
//		{
//			dp[j] = dp[j] || dp[j - arr[i]];
//		}
//	}
//	return dp[sum];
//}
//
//int main()
//{
//	cin >> x;
//	while (x > 0)
//	{
//		arr[n++] = x % 10;
//		sum += x % 10;
//		x /= 10;
//	}
//	cout << (func() ? "Yes" : "No") << endl;
//}